翻訳と辞書
Words near each other
・ カッティーノ・モブリー
・ カッテリーノ・カヴォス
・ カッテンストゥッツ
・ カッテンダイケ
・ カッテンディーケ
・ カッテンデイケ
・ カッテージチーズ
・ カッテージ・チーズ
・ カッディーシュ
・ カット
カット (グラフ理論)
・ カット (映画)
・ カット (曖昧さ回避)
・ カット (雑誌)
・ カット&ペースト
・ カットアウトスイッチ
・ カットアウト盤
・ カットアップ
・ カットアップ技法
・ カットアンドペースト


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

カット (グラフ理論) : ウィキペディア日本語版
カット (グラフ理論)
グラフ理論において、グラフ ''G''(''V'', ''E'') の頂点 ''V'' の 2 分割 (''S'', ''T'') をカット()とよぶ。このとき、ある辺 (''u'',''v'') \in ''E'' の端点が ''u'' \in ''S'' かつ ''v'' \in ''T''(有向グラフの場合 ''u'' \in ''T'' でかつ ''v'' \in ''S'' の場合もある)であるとき、この辺を「カットエッジ」と呼ぶ。
カットのサイズ (カットの重み) は、カットエッジの総数 (辺重みグラフの場合はカットエッジそれぞれの辺重みの総和) で表される。フローネットワークでは、カットのサイズは始点側から終点側へ向かう辺重みの総和で定義される(逆方向のエッジは加算されない)。
頂点集合のべき集合を定義域としたカットのサイズを返す集合関数は「カット関数」と呼ばれ、
劣モジュラ関数、かつ、正モジュラ関数である。
== 最小カットと最大カット ==


抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「カット (グラフ理論)」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.